//
//  BinarySearchTree.swift
//  数据结构与算法
//
//  Created by Rowling on 2024/2/22.
//

import Foundation


class BinarySearchTree<T : Comparable> : BinarySearchTreeInterface {
    
    typealias Visitor = ((_ e : T) -> Bool)
    
    var root : Node<T>?
    
    var size = 0
    
    func clear() {
        root = nil
        size = 0
    }
    
    func isEmpty() -> Bool {
        return size == 0;
    }
    
    func add(element: T) {
        // 判断根节点
        size += 1
        guard let root = root else {
            self.root = createNode(element: element)// Node(element: element)
            afterAdd(node: self.root!)
            return
        }
        let newNode = createNode(element: element)
        let addnode = addFind(node: root, newNode: newNode)
        afterAdd(node: addnode)
    }
    
    func createNode(element: T, left: Node<T>? = nil, right: Node<T>? = nil, parent: Node<T>? = nil) -> Node<T> {
        return Node(element: element, left: left, right: right, parent: parent)
    }
    
    func afterAdd(node : Node<T>) {
        
    }
    
    private func addFind(node : Node<T>, newNode : Node<T>) -> Node<T> {
        var addNode = newNode
        if node.element < newNode.element {
            if let n = node.right {
                addNode = addFind(node: n, newNode: newNode)
            } else {
                node.right = newNode
                newNode.parent = node
            }
        } else if (node.element == newNode.element) {
            node.element = newNode.element
            size -= 1
            addNode = node
        } else {
            if let n = node.left {
                addNode = addFind(node: n, newNode: newNode)
            } else {
                node.left = newNode
                newNode.parent = node
            }
        }
        return addNode
    }
    
    // 查询节点
    private func findNode(element : T) -> Node<T>? {
        var node : Node<T>?
        node = root
        while (node != nil) {
            if node!.element < element {
                node = node!.right
            } else if (node!.element == element) {
                return node
            } else {
                node = node!.left
            }
        }
        return nil
    }
    
 
    // 移除节点
    func remove(element: T) {
        guard let node = findNode(element: element) else { return }
        remove(node: node)
    }
    
    func reomveV2(node : Node<T>) {
        size -= 1
        var node = node
        if node.subNodeCount == 2 {
            guard let preorder = successor(no: node) else {return}
            node.element = preorder.element
            node = preorder    
        }
        var replacement = node.left != nil ? node.left : node.right
        if let replacement = replacement {
            
        } else {
            
        }
    }
    
    func remove(node : Node<T>) {
        var node = node
        size -= 1
        if node.subNodeCount == 2 {
            guard let preorder = successor(no: node) else {return}
            node.element = preorder.element
            node = preorder
        }
        // 如果是叶子结点
        if node.isLeaf {
            if node === root {
                root = nil
            }
            if let parent = node.parent {
                if parent.left === node {
                    parent.left = nil
                } else if parent.right === node {
                    parent.right = nil
                }
            }
            afterRemove(node: node)
        } else if node.subNodeCount == 1 {
            var subNode : Node<T>?
            if let right = node.right {
                subNode = right
            }
            if let left = node.left  {
                subNode = left
            }
            subNode?.parent = nil
            // 度为1
            if node === root {
                // 为根节点
                root = subNode
            } else {
                if node.parent?.left === node {
                    node.parent?.left = subNode
                    subNode?.parent = node.parent
                }
                if node.parent?.right === node {
                    node.parent?.right = subNode
                    subNode?.parent = node.parent
                }
            }
            afterRemove(node: node, replacement: subNode)
        }
    }
    
    func afterRemove(node : Node<T>, replacement : Node<T>? = nil) {
        
    }
    
    func contains(element: T) -> Bool {
        findNode(element: element) == nil
    }
    
    /// 前序遍历
    func preorderTraversal() {
        if let root = root {
            preorderTraversal(node: root)
        }
    }
    
    func preorderTraversal(node : Node<T>) {
        print(node.element)
        if let left = node.left {
            preorderTraversal(node: left)
        }
        if let right = node.right {
            preorderTraversal(node: right)
        }
    }
    
    /// 中序遍历
    func inorderTraversal(visitor: Visitor) {
        if let root = root {
            inorderTraversal(node: root, visitor: visitor)
        }
    }
    
    func inorderTraversal(node : Node<T>, visitor : Visitor) {
        if let left = node.left {
            inorderTraversal(node: left, visitor: visitor)
        }
        if visitor(node.element) {
            return
        }
        if let right = node.right {
            inorderTraversal(node: right, visitor: visitor)
        }
    }
    
    /// 后序遍历
    func postorderTraversal() {
        if let root = root {
            postorderTraversal(node: root)
        }
    }
    
    func postorderTraversal(node : Node<T>) {
        if let left = node.left {
            postorderTraversal(node: left)
        }
        if let right = node.right {
            postorderTraversal(node: right)
        }
        print(node.element)
    }
    
    /// 层序遍历
    func levelorderTraversal(visitor : Visitor) {
        guard let root = root else {return}
        var queue = [root]
        while !queue.isEmpty {
            if let node = queue.first {
                if visitor(node.element) {
                    // 看前驱
//                    print(predecessor(no: node)?.element)
                    // 看后继
//                    print(successor(no: node)?.element)
                    return
                }
                queue.remove(at: 0)
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
        }
    }
    
    /// 获取一个二叉树的高度
    func height() -> Int {
        // 递归
        return height(root)
        
        // 层序遍历
//        guard let root = root else {return 0}
//        var queue = [root]
//        var layer = 0
//        while (!queue.isEmpty) {
//            var temp = queue
//            queue.removeAll()
//            for node in temp {
//                if let left = node.left {
//                    queue.append(left)
//                }
//                if let right = node.right {
//                    queue.append(right)
//                }
//            }
//            layer += 1
//        }
//        return layer
    }
    
    // 递归求高度
    func height(_ node : Node<T>?) -> Int {
        guard let node = node else {return 0}
        return 1 + max(height(node.left), height(node.right))
    }
    
    
    // 判断是否是完全二叉树
    func isComplete() -> Bool {
        guard let root = root else {return false}
        var queue = [root]
        var leaf = false
        while !queue.isEmpty {
            let temp = queue
            queue.removeAll()
            for n in temp {
                if leaf && (n.left != nil || n.right != nil){
                    return false
                }
                if let left = n.left {
                    queue.append(left)
                } else if n.right != nil {
                    return false
                }
                if let right = n.right {
                    queue.append(right)
                } else {
                    leaf = true
                }
            }
        }
        return true
    }
    
    
    func printInfo() -> [[Node<T>?]] {
        var infoArray = [[Node<T>?]]()
        guard let root = root else {return infoArray}
        var queue : [Node<T>?] = [root]
        var layer = 0
        var notEmptyFlag = true
        while (notEmptyFlag) {
            var temp = queue
            infoArray.append(temp)
            queue.removeAll()
            for node in temp {
                if let node = node {
                    queue.append(node.left)
                    queue.append(node.right)
                } else {
                    queue.append(nil)
                    queue.append(nil)
                }
            }
            notEmptyFlag = (queue.first(where: {$0 != nil}) != nil)
        }
        return infoArray
    }
    
    func reverseTree() {
        reverseTree(node: root)
    }
    
    // 翻转二叉树
    func reverseTree(node : Node<T>?) {
        guard let node = node else {return}
        let temp = node.left
        node.left = node.right
        node.right = temp
        reverseTree(node: node.right)
        reverseTree(node: node.left)
    }
    
    // 前驱节点
    func predecessor(no : Node<T>?) -> Node<T>? {
        guard let no = no else {return nil}
        if let left = no.left {
            var preNode = left
            while preNode.right != nil {
                preNode = preNode.right!
            }
            return preNode
        } else {
            var node = no.parent
            while (node?.parent != nil && node === node?.parent?.left) {
                node = node?.parent
            }
            return node?.parent
        }
    }
    
    // 后继节点
    func successor(no : Node<T>?) -> Node<T>? {
        guard let no = no else {return nil}
        if let right = no.right {
            var preNode = right
            while preNode.left != nil {
                preNode = preNode.left!
            }
            return preNode
        } else {
            var node : Node<T>? = no
            while (node?.parent != nil && node === node?.parent?.right) {
                node = node?.parent
            }
            return node?.parent
        }
    }
}




